package org.nowcoder.leetcode.BTree;

import java.util.ArrayList;
import java.util.List;

/**
 * Title  : 257. Binary Tree Paths
 * Source : https://leetcode.cn/problems/binary-tree-paths/
 * Author : XrazYang
 * Date   : 2023-09-09
 */

public class LeetCode_257 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List<String> binaryTreePaths(TreeNode root) {
        // 非递归实现
        // List<String> results = new ArrayList<>();
        // ArrayDeque<TreeNode> sta = new ArrayDeque<>();
        // ArrayDeque<String> pathSta = new ArrayDeque<>();
        // sta.push(root);
        // pathSta.push(String.valueOf(root.val));
        // while (!sta.isEmpty()) {
        //     TreeNode node = sta.pop();
        //     String path = pathSta.pop();

        //     if (node.left == null && node.right == null) {
        //         results.add(path);
        //     }

        //     //处理结点
        //     if (node.right != null) {
        //         sta.push(node.right);
        //         pathSta.push(path + "->" + node.right.val);
        //     }

        //     if (node.left != null) {
        //         sta.push(node.left);
        //         pathSta.push(path + "->" + node.left.val);
        //     }
        // }
        // return results;


        //递归实现
        List<String> results = new ArrayList<>();
        dfs(root, "", results);
        return results;
    }

    private void dfs(TreeNode root, String path, List<String> results) {
        if (root != null) {
            StringBuilder builder = new StringBuilder(path);
            builder.append(root.val);
            if (root.left == null && root.right == null) {
                results.add(builder.toString());
            } else {
                builder.append("->");
                dfs(root.left, builder.toString(), results);
                dfs(root.right, builder.toString(), results);
            }
        }
    }
}
